package Z.dailyExercise.May;

import java.util.EventListener;

public class _1482制作m束花所需的最少天数 {

    /*
    如果数组长度小于总花数 必然无法制作
    题解：思路转化为二分查找：寻找一个天数 使得这个天数中盛开的连续的花可以制作需要的花的数量

    查找一个数  判断一线能否做花束 其中用一个参数来计数 判断是否连续
    等于所需的m 或者出现非盛开时 直接清零

     */
    public int minDays(int[] bloomDay, int m, int k) {
        if(bloomDay== null || bloomDay.length<m*k){
            return -1;
        }
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i]>max){
                max = bloomDay[i];
            }
            if (bloomDay[i]<min){
                min = bloomDay[i];
            }
        }

        while (min <max){
            int day = min + (max-min)/2;
            if (canMake(bloomDay,m,k,day)){
                max = day;

            }else {
                min = day+1;
            }


        }

        return min;


    }

    public boolean canMake(int[] bloomDay, int m, int k,int day){
        int count =0;//计算花束
        int flower =0;//计算盛开的数量
        for (int i = 0; i < bloomDay.length && count< m; i++) {
            if (bloomDay[i] <= day){
                flower++;
                if (flower == k){
                    count++;
                    flower =0;
                }
            }else {
                flower =0;
            }
        }

        return count>= m;

    }
}
